The invention relates generally to the art of digital communications and more specifically to a system for minimizing the average latency in transporting messages, such as packets or frames, which are segmented into a plurality of smaller cells for transport across a network.
Asynchronous transfer mode (hereinafter xe2x80x9cATMxe2x80x9d) service inter-networking protocols enable data or messages formatted according to a non-ATM data communication protocol to be transported across an ATM network. For example, the Frame Relay Forum FRF.5 protocol specifies how a relatively large, variable length, frame relay packet should be segmented into a plurality of ATM-like, fixed-size, cells for transport across an ATM network. Such protocols necessarily define how the ATM Adaption Layer (AAL) should be provisioned since this layer of the ATM/B-ISDN protocol stack, as defined by ITU Recommendation I.321 and shown in FIG. 1, is responsible for adapting the services provided by the ATM Layer, which provides basic ATM cell transport functions, to higher layers, e.g. frame relay bearer service.
FIG. 2 illustrates a generic version of the AAL in greater detail. As shown in FIG. 2, some versions of the AAL, such as AAL3/4 and AAL5, include a convergence sublayer (CS) and a segmentation and reassembly sublayer (SAR). The CS, which sits directly above the SAR and below the AAL Service Access Point (SAP), aligns the SDUs and adds overhead information. The CS may also provide service specific signalling or data link functions.
The SAR, when operating in a message mode, segments a single AAL SAR Service Data Unit (hereinafter xe2x80x9cSDUxe2x80x9d), such as a variable length frame packet, into a plurality of AAL SAR Protocol Data Units (hereinafter xe2x80x9cPDUxe2x80x9d), each of which essentially forms the payload of an ATM cell transmitted across an ATM network. Conversely, at the destination, the destination SAR requires that all of the PDUs composing an SDU be passed from the ATM Layer to the destination SAR before it can reassemble the SDU and, ignoring the role of the convergence sublayer, indicate reception of the SDU to the higher layer using the AAL. Thus, the latency in transmitting an SDU from a first point to a second point in a network can be defined as the time from which the transmission of the SDU is first requested until the time the last PDU arrives at the destination SAR and the SDU is reassembled. In other words, latency can be defined as the time required to transmit the SDU from an originating AAL SAP to a destination AAL SAP. This latency is entirely characterized by the amount of time required to propagate the last PDU of an SDU across the ATM networkxe2x80x94the time required to propagate any other PDU before the last PDU of an SDU is of no consequence at the destination AAL SAP.
Latency manifests itself as sluggishness or slow response time in interactive-type communications. For example, if one were sending joystick instructions across a network during the course of an interactive game played there over, a long latency would, in the absence of other aggravating factors, result in a noticeable time period between the physical movement of the joystick and the corresponding computer action. Accordingly, it is desirable to minimize latency for interactive telecommunications applications.
Latency is affected by the service discipline used to schedule or multiplex PDUs corresponding to SDUs from a plurality of virtual connections (VCs) into a single cell stream for transmission across the Physical Layer (PHY) of the ATM network. FIG. 3 shows how an ATM Layer 11 provides a SAP 10 to each of several VCs, each of which has its own AAL 12 (i.e., the AAL is invoked in parallel instances). The ATM Layer 11, in turn, uses a single SAP 14 into a PHY 16. One role of the ATM Layer 11 is to accept requests of PDUs 17 from each SAP 10 and to multiplex these PDUs into a single cell stream 18 such that the timing of the transmission of each of the PDUs conforms to predetermined traffic parameters assigned to its respective VC.
FIG. 3 illustrates a condition where each VC generates a burst 20 of several ATM PDU requests at the ATM SAP 10, wherein each such burst corresponds to a single SDU 22, such that there is an overlap in the transmission periods of the SAR SDUs from the ATM Layer 11 to the PHY 16. The ATM PDUs 17 received from the ATM SAP 10 must therefore be queued, and then the ATM PDUs from each of the different ATM SAPs 10 must be multiplexed in some order onto the single stream 18 of ATM PDUs passed to the PHY SAP 14. Given this set of PDUs which have been requested over several ATM Layer SAPs 10, and subject to the constraints of satisfying the traffic parameters of each VC, it is often desired to minimize the average amount of latency experienced per unit of SDU data (i.e., per PDU) for various types of ATM service categories.
As shown in FIG. 3, a typical ATM Layer implementation might use round-robin ordering in sending the PDUs 17 to the PHY SAP 14 from each ATM SAP 10. This would result in each corresponding SDU 22 using an equal fraction of the PHY bandwidth while the PDUs for each SDU are being transmitted. This is shown, for instance, in the bandwidth occupancy chart of FIG. 4A for the situation where two VCs each request a burst of the same number of PDUs at about the same time, wherein each VC has a PCR equal to 100% of the available bandwidth. (A xe2x80x9cbandwidth occupancy chartxe2x80x9d is a chart with time on the horizontal axis, and bandwidth on the vertical axis. Each SDU sent on an ATM virtual connection is shown as a shaded region on such a chart. The net height of the region at a particular time shows the amount of bandwidth occupied by the transmission of the SDU at that time; the leftmost and rightmost extent of the region gives the time at which the first and last PDUs for the SDU are transmitted, respectively; and the total area of the region gives the size of the SDU. Unshaded regions in these charts represent the proportion of unused PHY bandwidth, for which the ATM Layer will be sending idle cells.) This ordering is not optimal with respect to the average amount of latency experienced per unit of SDU data.
Broadly speaking, the invention seeks to minimize or reduce the average per unit latency in transporting messages which are decomposed into a plurality of smaller data units for transport across a network.
One aspect of the invention relates to an apparatus for transmitting messages associated with a plurality of variable bit rate connections, each of which is associated with a traffic contract which defines compliance thereto as conformance to a leaky bucket algorithm. The apparatus comprises transmission equipment for receiving multiple messages, segmenting each received message into one or more data units, and multiplexing such data units from various connections into a single stream for transport over a physical interface at an output transmission rate. A bandwidth allocation means is associated with the transmission equipment for dynamically allocating a portion of the output transmission rate to any connection. A scheduler is connected to the bandwidth allocation means for scheduling the transfer of messages to the single stream of the transmission equipment and for allocating a portion of the output transmission rate to each connection at the time its message is transferred to the transmission equipment. The portion of the output transmission rate for a given connection is substantially equal to 1/T, T being computed as       T    ←          max      ⁡              (                                            T              S                        +                                          X                -                                  τ                  S                                                            N                -                1                                              ,                      T            p                    ,                      T            L                          )              ,            if      ⁢                        xe2x80x83                ⁢                  xe2x80x83                    ⁢      N         greater than     1  
and
T←max(Tp, TL), if N=1
where TS is a period corresponding to a constant sustained transmission rate, Tp is a period corresponding to a peak transmission rate, xcfx84S is a burst tolerance, N is the number of data units in the message, X is a fill level of the leaky bucket associated with the given connection, and TL corresponds to all unused bandwidth allocated to a service class to which the given connection belongs.
Another aspect of the invention relates to an apparatus for transmitting messages associated with a plurality of variable bit rate connections, each of which is associated with a traffic contract which defines compliance thereto as conformance to a leaky bucket algorithm. The apparatus comprises transmission equipment for receiving multiple messages, the transmission equipment including a segmentation means for segmenting each received message into one or more data units and a multiplexing means for multiplexing such data units from various connections into a single stream for transport over a physical interface at an output transmission rate. A bandwidth allocation means is associated with the transmission equipment for dynamically allocating a portion of the output transmission rate to any connection. A scheduler, connected to the bandwidth allocation means, is provided for scheduling the transfer of messages to the single stream of the transmission equipment. The scheduler preferably transfers messages to the single stream of the transmission equipment by receiving the messages from higher layer networking services and transferring the messages to the segmentation means which substantially immediately transfers the messages to the multiplexing means. Alternatively, the scheduler may transfer messages to the single stream of the transmission equipment by receiving the data units from the segmentation means and transferring groups of data units to the multiplexing means, wherein each such group corresponds to a message. The scheduler is enabled to transfer the messages according to an order corresponding to the level of a leaky bucket associated with each corresponding connection in order to reduce the interleaving of data units from various connections over the single stream.
In the preferred embodiment, the transmission equipment comprises a segmentation means and a multiplexing means for respectively segmenting each received message into data units and multiplexing the data units into the aforesaid single stream. The scheduler preferably transfers messages to the single stream of the transmission equipment by receiving the messages from higher layer networking services and transferring the messages to the segmentation means which substantially immediately transfers the messages to the multiplexing means. Alternatively, the scheduler may transfer messages to the single stream of the transmission equipment by receiving the data units from the segmentation means and transferring groups of data units to the multiplexing means, wherein each such group corresponds to a message.
In the preferred embodiment, the transmission equipment includes an indication means for informing the scheduler when a message has been fully transmitted by the transmission equipment. When indication means is actuated, the scheduler is enabled to set a new transmission rate for a given connection during the time a message associated therewith is in the process of being transmitted by the transmission equipment. The new transmission rate is substantially equal to 1/T, T being computed as       T    ←          max      ⁡              (                                            T              S                        +                                                            X                  est                                -                                  τ                  S                                                                              R                  est                                -                1                                              ,                      T            p                    ,                      T            L                          )              ,      xe2x80x83    ⁢            if      ⁢              xe2x80x83            ⁢              R        est               greater than     1    ,
where Xest and Rest respectively represent an expected bucket fill level and an estimated number of data units remaining to be transmitted in the message for the given connection.
The most preferred embodiment relates to an ATM communications device wherein the messages are ATM adaption layer (AAL) service data units (SDUs) associated with a plurality of virtual circuit connections, and the data units are AAL segmentation and reassembly protocol data units (SAR PDUs). The transmission equipment preferably comprises segmentation means for segmenting each AAL SDU into one or more SAR PDUs, ATM layer means for multiplexing the SAR PDUs of various connections into a single stream having an output transmission rate, and physical transmission means, connected to the ATM layer means, for transporting the single stream of SAR PDUs over a physical interface.
Another aspect of the invention relates to a method for transmitting multiple messages associated with multiple variable bit rate connections over a network, wherein each such connection is associated with a traffic contract which defines compliance thereto as conformance with a leaky bucket algorithm. The method comprises the steps of:
(a) segmenting each message of each connection into one or more transportable data units;
(b) multiplexing the data units from various connections into a single stream for transport over a transmission media to a destination;
(c) scheduling the transfer of messages from the multiple connections to the multiplexing step; and
(d) allocating a portion of the transmission media bandwidth to each connection substantially when its message is transferred to the multiplexing step, said portion of the transmission media bandwidth for a given connection being substantially equal to 1/T, T being computed as       T    ←          max      ⁡              (                                            T              S                        +                                          X                -                                  τ                  S                                                            N                -                1                                              ,                      T            p                    ,                      T            L                          )              ,            if      ⁢                        xe2x80x83                ⁢                  xe2x80x83                    ⁢      N         greater than     1  
and
T←max(Tp, TL), if N=1
where TS is a period corresponding to a constant sustained transmission rate, Tp is a period corresponding to a peak transmission rate, xcfx84S is a burst tolerance, N is the number of data units in the message, X is a fill level of the leaky bucket associated with the given connection, and TL corresponds to all unused bandwidth allocated to a service class to which the given connection belongs.
Another aspect of the invention relates to a method for transmitting multiple messages associated with multiple variable bit rate connections over a network, wherein each such connection is associated with a traffic contract which defines compliance thereto as conformance with a leaky bucket algorithm. The method comprises the steps of:
(a) segmenting each message of each connection into transportable data units;
(b) multiplexing the data units from various connections into a single stream for transport over a transmission media to a destination;
(c) scheduling the transfer of messages from the multiple connections to the multiplexing step; and
(d) wherein the scheduling step includes one of:
(i) scheduling the transfer of groups of data units from the segmentation step to the multiplexing step, wherein each such group of data units corresponds to a message, and
(ii) scheduling the transfer of messages from the multiple connections to the segmentation step, wherein the segmentation step substantially immediately transfers the data units to the multiplexing step; and
wherein the scheduling step is enabled to transfer the messages according to an order corresponding to the level of a leaky bucket associated with each corresponding connection in order to reduce the interleaving of data units from various connections over said single stream.